The present invention relates to a method of automatically deciding wiring routes between terminals on a printed-circuit board or the like. The present invention ensures the requisite thicknesses of the wires and the minimum spacing between wires and confirms that a limitation on the capacity of a wiring route is not exceeded.
The capacity of a wiring route between terminals on a printed-circuit board is based on the required width of the wires, the minimum separation distance between wires, the number of wires required and the space available. Some of the wiring routes are predetermined and viewed as "obstacles" during the subsequent process of laying out the remaining wires. Previously known automatic wiring systems can re-position, by a "push-away" operation, a predetermined wiring route to make room for another wire. When the predetermined wire route is 90.degree. or 45.degree. relative to the new wire, it is possible with conventional routing systems to dynamically re-position the predetermined wire route in a reasonable amount of time. However, it-is not practical using conventional routing systems to re-position a predetermined wire route which lies at other, "free" angles relative to the new wire due to complexity of the calculations required.
A "rubber band" model has also been used to determine wire routing where there are previously wired lines. The rubber band model is representative of routes topologically equivalent and is expressed by a series of "critical cuts". Each critical cut connects two objects in the shortest distance and is considered a line tightly extended between two terminals. If each critical cut does not exceed the wiring capacity, physical positioning of all the wires can be accomplished while meeting the wiring capacity as a whole. See E. Leiserson and F. M. Maley, "Algorithms for Routing and Testing Routability of Planar VLSI layouts," Proc. STOC, pp. 69-78 (1985). Consequently, in the rubber band model the physical position of a previously wired line is not determined during route search for wiring, but it is determined by checking the physical wiring possibility with detailed wiring process after the position of all other wiring routes has been determined.
It is possible and common to convert another type of route expression to a rubber band model in real time. Then an accurate route capacity can be verified by a visibility graph or mesh structure obtained by region segmentation. However, only an approximate route capacity can be estimated automatically with conventional computer systems in a reasonable amount of time because of the complexity of calculating the capacities of all critical cuts. When there is excess room in a wiring region, the approximate determinations of capacity can obtain viable wiring routes. However, many printed circuit boards today have high density, and wiring is required to the very limit of the capacity. Therefore, for typical high-density wiring requirements, conventional routing systems require too much time to make free-angle adjustments between new wires and previously determined wire routes.